package interview.tree;

//遍历
public class TreeTraversal
{
	// 前序遍历
	public void preOrder(TreeNode root)
	{
		// 处理特殊值
		if (root == null)// 空树
		{
			return;// 什么都不能输出
		}

		// 先遍历根:输出
		System.out.print(root.getValue());
		// 前序遍历左子树
		preOrder(root.getLeft());
		// 前序遍历右子树
		preOrder(root.getRight());
	}

	// 中序遍历
	public void inOrder(TreeNode root)
	{
		// 处理特殊值
		if (root == null)// 空树
		{
			return;// 什么都不能输出
		}

		// 先中序遍历左子树
		inOrder(root.getLeft());
		// 遍历根:输出
		System.out.print(root.getValue());
		// 中序遍历右子树
		inOrder(root.getRight());
	}

	// 后序遍历
	public void postOrder(TreeNode root)
	{
		// 处理特殊值
		if (root == null)// 空树
		{
			return;// 什么都不能输出
		}

		// 先后序遍历左子树
		postOrder(root.getLeft());
		// 后序遍历右子树
		postOrder(root.getRight());
		// 遍历根:输出
		System.out.print(root.getValue());
	}

	public static void main(String[] args)
	{
		TreeCreator creator = new TreeCreator();
		TreeTraversal traversal = new TreeTraversal();

		TreeNode sampleTree = creator.createSampleTree();

		// 先序遍历
		traversal.preOrder(sampleTree);
		System.out.println();

		// 中序遍历
		traversal.inOrder(sampleTree);
		System.out.println();

		// 后序遍历
		traversal.postOrder(sampleTree);
		System.out.println();
	}

}
